#include <vector>
#include <list>

#include "cover.h"

using std::vector;
using std::list;

/**
 * Greedy algorithm based on VERTEX COVER
 * Modifies: matrix, cover, solutions
 *
 * @param   matrix  the 0,1 matrix represented as vector of vectors of int
 * @param   ncols   number of data columns representing lines,
 *		    not number of characters
 * @param   nrows   number of rows
 * @param   cover   int array of length ncols
 * @param   solutions	a storage container for solution row indices
 */
void greedy_vc (
	vector<vector<int> > &matrix,
	size_t nrows,
	size_t ncols,
	int *cover,
	list<int> &solutions
	)
{
    /**
     * Algorithm description
     *
     * while not finished covering
     *. count the number of 1's in each column
     *. find the uncovered column with smallest column sum
     *. for all rows covering that column (i.e. containing a 1 in that column),
     *	 - add the row to the solution set
     *	 - cover the matrix with that row
     */

    int *colsums = new int[ncols];	// for greediness counting

    // initialize colsums: count the 1's in each column
    initialize_row_column_sums (matrix, NULL, colsums);

    while ( !finished(cover, ncols) ) {
	// find min col that has NOT been covered yet
	// !finished() guarantees one exists
	int colj, mincolj;
	colj = mincolj = 0;
	while (colj < ncols) {
	    if ( (cover[mincolj] == 1) || // if mincolj is covered, advance it
		    (cover[colj] != 1) && (colsums[mincolj] > colsums[colj]) )
	    {
		mincolj = colj;
	    }
	    ++colj;
	}
	// POST: mincolj == index of minimum uncovered column sum

	// temporary storage for rows to cover
	vector<int> row_indices;
	int endrow = matrix.size();

	// save all indices of rows i with a 1 in mincol 
	// if we cover matrix here, all other 1's in the column are lost
	// so we save all the row indices first
	for (int i=0; i<endrow; i++) {
	    if ( matrix.at(i).at(mincolj) == 1 ) {
		solutions.push_back(i);
		row_indices.push_back(i);
	    }
	}
	// cover now
	vector<int>::iterator itr = row_indices.begin();
	vector<int>::iterator enditr = row_indices.end();
	while (itr != enditr) {
	    // cover matrix
	    cover_with_row (matrix, *itr, cover, NULL, colsums);
	    ++itr;
	}
    }

    /* clean up duty -- free up memory */
    delete[] colsums;
}

